package DataStructure.heapStackQueue.queue;


import java.util.*;

public class SlideWindows {

    public static void main(String[] args) {
        SlideWindows s = new SlideWindows();
        int[] array = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int[] ans = s.GetSlideMax(array, 3);
        for (int an : ans) {
            System.out.print(an + " ");
        }
    }

    public int[] GetSlideMax(int[] array, int k) {
        if (array == null || array.length <= k) {
            return array;
        }
        Deque<Integer> queue = new LinkedList<>();
        // 存放下标地址，便于越界判断
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && array[i] >= array[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        int[] answer = new int[array.length - k + 1];
        answer[0] = array[queue.peekFirst()];
        for (int i = k; i < array.length; i++) {
            // 当队列尾元素 小于 当前值
            while (!queue.isEmpty() && array[i] >= array[queue.peekLast()]) {
                queue.pollLast();
            }
            // 再次判断：当队列首元素超出 k 的范围，逐个弹出
            while (!queue.isEmpty() && queue.peekFirst() <= i - k) {
                queue.pollFirst();
            }
            // 存入当前值
            queue.offerLast(i); // tips:存入的是坐标
            answer[i - k + 1] = array[queue.peekFirst()];
        }
        return answer;
    }
}
